package com.company.Sort;

/**
 * Created by v on 16-12-10.
 */
public class MergeSort {
    //不允许创建其对象
    private void MergeSort(){}

    public static<E extends Comparable<E>> void mergeSort(E[] array){
        E[] tempArray=(E[]) new Comparable[array.length];

        mergeSort(array,tempArray,0,array.length-1);
    }

    //递归调用排序算法
    private static<E extends Comparable<E>> void mergeSort
            (E[] array,E[] tempArray,int left,int right){

        int center=(left+right)/2;

        if(left<right){
            mergeSort(array,tempArray,left,center);
            mergeSort(array,tempArray,center+1,right);
            merge(array,tempArray,left,center+1,right);
        }
    }

    //合并两个有序数组
    private static <E extends Comparable<E>> void merge
            (E[] array,E[] tempArray,int leftPos,int rightPos,int rightEnd){
        int leftEnd=rightPos-1;
        int tempPost=leftPos;
        int numElements=rightEnd-leftPos+1;

        while (leftPos<=leftEnd&&rightPos<=rightEnd){
            if(array[leftPos].compareTo(array[rightPos])<0){
                tempArray[tempPost++]=array[leftPos++];
            }else {
                tempArray[tempPost++]=array[rightPos++];
            }
        }

        while (leftPos<=leftEnd){
            tempArray[tempPost++]=array[leftPos++];
        }

        while (rightPos<=rightEnd){
            tempArray[tempPost++]=array[rightPos++];
        }

        for(int i=0;i<numElements;i++,rightEnd--){
            array[rightEnd]=tempArray[rightEnd];
        }
    }
}
